/**
 * 538. 把二叉搜索树转换为累加树
 * https://leetcode-cn.com/problems/convert-bst-to-greater-tree/
 */
const { createTreeNode, displayTreeNode } = require('../../libs/public');

/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
function convertBST(root) {
  if (!root) {
    return root;
  }
  const stack = [];
  let node = root;
  let sum = 0;
  while (node) {
    while (node.right) {
      stack.push(node);
      node = node.right;
    }
    while (node && !node.left) {
      sum += node.val;
      node.val = sum;
      node = stack.pop();
    }
    if (!node) {
      break;
    }
    sum += node.val;
    node.val = sum;
    node = node.left;
  }
  return root;
}

console.log(displayTreeNode(
  convertBST(createTreeNode(
    [4, 1, 6, 0, 2, 5, 7, null, null, null, 3, null, null, null, 8],
  )),
) === '[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]');
console.log(displayTreeNode(
  convertBST(createTreeNode(
    [0, null, 1],
  )),
) === '[1,null,1]');
console.log(displayTreeNode(
  convertBST(createTreeNode(
    [1, 0, 2],
  )),
) === '[3,3,2]');
console.log(displayTreeNode(
  convertBST(createTreeNode(
    [3, 2, 4, 1],
  )),
) === '[7,9,4,10]');
console.log(displayTreeNode(
  convertBST(createTreeNode(
    [],
  )),
) === '[]');
